package org.example.dynamic_planning;

import java.util.Arrays;
import java.util.Scanner;

public class Complete_backpack {
    public static void main(String[] args) {
        //完全背包

        //题目描述
        //小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。
        //小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。
        //输入描述
        //第一行包含两个整数，N，V，分别表示研究材料的种类和行李空间
        //接下来包含 N 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值
        //输出描述
        //输出一个整数，表示最大价值。
        //输入示例
        //4 5
        //1 2
        //2 4
        //3 4
        //4 5
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int v = sc.nextInt();
        int[] dp = new int[v + 1];
        int[] weight = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= v; j++) {
                if (weight[i] <= j)
                    dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
//            System.out.println(Arrays.toString(dp));
        }
        System.out.println(dp[v]);
    }
}
